﻿using System.Text;

namespace DataStructure;

//循环数组
public class CirSeqList<E> : IFifoList<E>
{
    private E[] data;
    private int first;
    private int last;
    private int N;

    public CirSeqList(int capacity)
    {
        data = new E[capacity];

        first = 0;
        last = 0;
        N = 0;
    }

    public CirSeqList() : this(10) { }

    public int Count => N;
    public bool IsEmpty => N == 0;

    public void AddLast(E e)
    {
        if (N == data.Length)
        {
            ResetCapacity(2 * data.Length);
        }

        data[last] = e;
        last = (last + 1) % data.Length;
        N++;
    }

    public E RemoveFirst()
    {
        if (IsEmpty)
        {
            throw new InvalidOperationException("数组为空");
        }

        E ret = data[first];
        data[first] = default;

        first = (first + 1) % data.Length;
        N--;

        if (N == data.Length / 4)
        {
            ResetCapacity(data.Length / 2);
        }

        return ret;
    }

    private void ResetCapacity(int newCapacity)
    {
        E[] newData = new E[newCapacity];

        for (int i = 0; i < N; i++)
        {
            newData[i] = data[(first + i) % data.Length];
        }

        data = newData;
        first = 0;
        last = N;
    }

    public E GetFirst()
    {
        if (IsEmpty)
        {
            throw new InvalidOperationException("数组为空");
        }

        return data[first];
    }

    //清空循环顺序表
    public void Clear()
    {
        data = new E[10];

        first = 0;
        last = 0;
        N = 0;
    }

    public override string ToString()
    {
        StringBuilder res = new StringBuilder();

        res.Append("[");
        for (int i = 0; i < N; i++)
        {
            res.Append(data[(first + i) % data.Length]);
            if ((first + i) % data.Length != last - 1)
                res.Append(", ");
        }
        res.Append("]");

        return res.ToString();
    }
}
